from typing import List

MOD = 10 ** 9 + 7


class Solution:
    def numberWays(self, hats: List[List[int]]) -> int:
        n = len(hats)
        hats = [set(hat) for hat in hats]

        dp1 = [0] * (1 << n)
        dp1[0] = 1

        for i in range(1, 41):
            # 统计谁喜欢这顶帽子
            who_like = []
            for j in range(n):
                if i in hats[j]:
                    who_like.append(j)

            # 如果没有人喜欢这顶帽子
            if not who_like:
                continue

            dp2 = list(dp1)

            for mask in range(1 << n):
                for j in who_like:
                    if not mask & (1 << j):
                        # print(mask, j, [i - 1, mask], "->", [i, mask | (1 << j)])
                        dp2[mask | (1 << j)] = (dp2[mask | (1 << j)] + dp1[mask]) % MOD

            dp1 = dp2

        return dp1[-1] % MOD


if __name__ == "__main__":
    print(Solution().numberWays([[3, 4], [4, 5], [5]]))  # 1
    print(Solution().numberWays([[3, 5, 1], [3, 5]]))  # 4
    print(Solution().numberWays([[1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4]]))  # 24
    print(Solution().numberWays([[1, 2, 3], [2, 3, 5, 6], [1, 3, 7, 9], [1, 8, 9], [2, 5, 7]]))  # 111
